import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindDuplicateSubtrees {

    List<TreeNode> ans;
    HashMap<String, Integer> map;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        ans = new ArrayList<>();
        map = new HashMap<>();
        dfs(root);
        return ans;
    }

    public String dfs(TreeNode node) {
        if (node == null) return "#";
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(node.val + ",");
        stringBuilder.append(dfs(node.left) + ",");
        stringBuilder.append(dfs(node.right));
        String s = stringBuilder.toString();
        map.put(s, map.getOrDefault(s, 0) + 1);
        if (map.get(s) == 2) ans.add(node);
        return s;
    }
}
